1. Technical Field
The present invention relates generally to antialiasing, and more specifically to an improved method of antialiasing using a bin database.
2. Description of Related Art
Background: 3D Computer Graphics
One of the driving features in the performance of most single-user computers is computer graphics. This is particularly important in computer games and workstations, but is generally very important across the personal computer market.
For some years, the most critical area of graphics development has been in three-dimensional (“3D”) graphics. The peculiar demands of 3D graphics are driven by the need to present a realistic view, on a computer monitor, of a three-dimensional scene. The pattern written onto the two-dimensional screen must, therefore, be derived from the three-dimensional geometries in such a way that the user can easily “see” the three-dimensional scene (as if the screen were merely a window into a real three-dimensional scene). This requires extensive computation to obtain the correct image for display, taking account of surface textures, lighting, shadowing, and other characteristics.
The starting point (for the aspects of computer graphics considered in the present application) is a three-dimensional scene, with specified viewpoint and lighting (etc.). The elements of a 3D scene are normally defined by sets of polygons (typically triangles), each having attributes such as color, reflectivity, and spatial location. (For example, a walking human, at a given instant, might be translated into a few hundred triangles which map out the surface of the human's body.) Textures are “applied” onto the polygons, to provide detail in the scene. (For example, a flat, carpeted floor will look far more realistic if a simple repeating texture pattern is applied onto it.) Designers use specialized modelling software tools, such as 3D Studio, to build textured polygonal models.
The 3D graphics pipeline consists of two major stages, or subsystems, referred to as geometry and rendering. The geometry stage is responsible for managing all polygon activities and for converting three-dimensional spatial data into a two-dimensional representation of the viewed scene, with properly-transformed polygons. The polygons in the three-dimensional scene, with their applied textures, must then be transformed to obtain their correct appearance from the viewpoint of the moment; this transformation requires calculation of lighting (and apparent brightness), foreshortening, obstruction, etc.
However, even after these transformations and extensive calculations have been done, there is still a large amount of data manipulation to be done: the correct values for EACH PIXEL of the transformed polygons must be derived from the two-dimensional representation. (This requires not only interpolation of pixel values within a polygon, but also correct application of properly oriented texture maps.) The rendering stage is responsible for these activities: it “renders” the two-dimensional data from the geometry stage to produce correct values for all pixels of each frame of the image sequence.
The most challenging 3D graphics applications are dynamic rather than static. In addition to changing objects in the scene, many applications also seek to convey an illusion of movement by changing the scene in response to the user's input. Whenever a change in the orientation or position of the camera is desired, every object in a scene must be recalculated relative to the new view. As can be imagined, a fast-paced game needing to maintain a high frame rate will require many calculations and many memory accesses.
Background: Texturing
There are different ways to add complexity to a 3D scene. Creating more and more detailed models, consisting of a greater number of polygons, is one way to add visual interest to a scene. However, adding polygons necessitates paying the price of having to manipulate more geometry. 3D systems have what is known as a “polygon budget,” an approximate number of polygons that can be manipulated without unacceptable performance degradation. In general, fewer polygons yield higher frame rates.
The visual appeal of computer graphics rendering is greatly enhanced by the use of “textures”. A texture is a two-dimensional image which is mapped into the data to be rendered. Textures provide a very efficient way to generate the level of minor surface detail which makes synthetic images realistic, without requiring transfer of immense amounts of data. Texture patterns provide realistic detail at the sub-polygon level, so the higher-level tasks of polygon-processing are not overloaded. See Foley et al., Computer Graphics: Principles and Practice (2.ed. 1990, corr. 1995), especially at pages 741-744; Paul S. Heckbert, “Fundamentals of Texture Mapping and Image Warping,” Thesis submitted to Dept. of EE and Computer Science, University of California, Berkeley, Jun. 17, 1994; Heckbert, “Survey of Computer Graphics,” IEEE Computer Graphics, November 1986, pp. 56; all of which are hereby incorporated by reference. Game programmers have also found that texture mapping is generally a very efficient way to achieve very dynamic images without requiring a hugely increased memory bandwidth for data handling.
A typical graphics system reads data from a texture map, processes it, and writes color data to display memory. The processing may include mipmap filtering which requires access to several maps. The texture map need not be limited to colors, but can hold other information that can be applied to a surface to affect its appearance; this could include height perturbation to give the effect of roughness. The individual elements of a texture map are called “texels”.
Awkward side-effects of texture mapping occur unless the renderer can apply texture maps with correct perspective. Perspective-corrected texture mapping involves an algorithm that translates “texels” (pixels from the bitmap texture image) into display pixels in accordance with the spatial orientation of the surface. Since the surfaces are transformed (by the host or geometry engine) to produce a 2D view, the textures will need to be similarly transformed by a linear transform (normally projective or “affine”). (In conventional terminology, the coordinates of the object surface, i.e. the primitive being rendered, are referred to as an (s,t) coordinate space, and the map of the stored texture is referred to a (u,v) coordinate space.) The transformation in the resulting mapping means that a horizontal line in the (x,y) display space is very likely to correspond to a slanted line in the (u,v) space of the texture map, and hence many additional reads will occur, due to the texturing operation, as rendering walks along a horizontal line of pixels.
One of the requirements of many 3-D graphics applications (especially gaming applications) is fill and texturing rates. Gaming and DCC (digital content creation) applications use complex textures, and may often use multiple textures with a single primitive. (CAD and similar workstation applications, by contrast, make much less use of textures, and typically use smaller polygons but more of them.) Achieving an adequately high rate of texturing and fill operations requires a very large memory bandwidth.
Background: Virtual Memory Management
One of the basic tools of computer architecture is “virtual” memory. This is a technique which allows application software to use a very large range of memory addresses, without knowing how much physical memory is actually present on the computer, nor how the virtual addresses correspond to the physical addresses which are actually used to address the physical memory chips (or other memory devices) over a bus.
Some further discussion of virtual memory management can be found in Hennessy & Patterson, Computer Architecture: A Quantititive Approach (2.ed. 1996); Hwang and Briggs, Computer Architecture and Parallel Processing (1984); Subieta, Object-Based Virtual Memory for PCs (1990); Carr, Virtual Memory Management (1984); Lau, Performance Improvement of Virtual Memory Systems (1982); and Loshin, Efficient Memory Programming (1998); all of which are hereby incorporated by reference. An excellent hypertext tutorial is found in the Web pages which start at http://cne.gmu.edu/Modules/VM/, and this hypertext tutorial is also hereby incorporated by reference. Another useful online resource is found at http://www.harlequin.com/mm/reference/faq.html, and this too is hereby incorporated by reference. Much current work can be found in the annual proceedings of the ACM International Symposium on Memory Management (ISMM), which are all hereby incorporated by reference.
Background: Buffering
A tiled, binning, chunking, or bucket rendering architecture is where the primitives are sorted into screen regions before they are rendered. This allows all the primitives within a screen region to be rendered together so as to exploit the higher locality of reference to the z buffer (an area in graphics memory reserved for z-axis values of pixels) and color buffers to give more efficient memory usage by typically just using on-chip memory. This also enables other whole-scene rendering opportunities such as deferred rendering, order independent transparency and new types of antialiasing.
The primitives and state (i.e., the rendering modes set up by the application, such as line width, point size, depth test mode, stencil mode, and alpha blending function) are recorded in a spatial database in memory that represents the frame being rendered. This is done after any transform and lighting (T&L) processing so everything is in screen coordinates. Ideally no rendering occurs until the frame is complete, however it will be done early on a user flush, if the amount of binned data exceeds a programmable threshold or if the memory set aside to hold the database is exhausted. While the database for one frame is being constructed the database for an earlier frame is being rendered.
The screen is divided up into rectangular regions called bins and each bin heads a linked list of bin records that hold the state and primitives that overlapped with this bin region. A primitive and its associated state may be repeated across several bins. Vertex data is held separately so it is not replicated when a primitive overlaps multiple bins and to allow more efficient storage mechanisms to be used. Primitives are maintained in temporal order within a bin.
Background: Antialiasing Using Super Sampling and Accumulation Buffering
Super sampling is a method of implementing full scene antialiasing where the scene is rendered to a higher resolution and then down filtered for display. The additional sample points are on a regular grid and the back buffer is enlarged to hold them. The pixels are then combined to form the final, lower resolution, antialiased image. Though super sampling can provide higher quality antialiasing, it also requires more memory and time, and needs at least 2× resolution in both x and y to look significantly better. Super sampling requires the color and depth buffers be held to a higher resolution so the memory footprint can become very large when many sample points per pixel are used.
Super sampling can be done without requiring the application to send the scene geometry multiple times. Normally a regular grid of sample points is used.
Higher quality antialiasing can be achieved by placing the sample points on an irregular, jittered, or stochastic grid. This prevents a slight movement of an edge from changing the coverage out of proportion, such as when several sample points like on a line parallel to the edge.
The accumulation buffer algorithm allows this type of stochastic super sampling to be implemented by rendering the geometry once per sample position with the corresponding sample jitter applied to the geometry via the projection matrix. Each pass is accumulated into an accumulation buffer and once complete, the accumulation buffer values are scaled for display. This has the advantage that the memory footprint is constant irrespective of the number of samples, unlike super sampling where the memory footprint is linear with the number of samples. Accumulation buffering also allows effects such as depth of field and motion blur to be included. The disadvantages of accumulation buffering is that it requires the application to render the scene multiple times, which taxes the application of the host system.
There is therefore a need in the art for an improved way to perform antialiasing that preferably can be done without taxing the application of the host computer system, which uses a relatively small (or static) memory footprint, and that allows for stochastic or otherwise irregular sample points to be used.
Stochastic Super Sampling or Automatic Accumulation Buffering
The present invention provides a novel way to perform rendering (in preferred embodiments, antialiasing) that implements a binning system. In one example embodiment, super sampling is used with accumulation buffering and a binning system to perform antialiasing that can be done behind the back of the application (i.e., it doesn't require the application to render the scene multiple times), that uses a small or static memory footprint, and that allows stochastic (i.e., irregular in some way) sample points to be used.
In one example embodiment, a method of rendering a scene comprises the steps of: rendering a full scene geometry; storing the geometry in a spatially sorted database; and rendering individual regions of the scene a plurality of times, wherein an offset is applied to pixel values of the scene before rendering. Other embodiments of the present innovations are described below.